package toOffer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/25 19:24
 * @description <p>环形链表</p>
 */
public class No141 {
    public static void main(String[] args) {
        int[] head = {3, 2, 0, -4};
        int pos = 1;

        //初始化链表
        ListNode node0 = new ListNode(3);
        ListNode node1 = new ListNode(2);
        node0.next = node1;
        ListNode node2 = new ListNode(0);
        node1.next = node2;
        ListNode node3 = new ListNode(-4);
        node2.next = node3;
        node3.next = node1;

        System.out.println(hasCycle1(node0));
    }

    /**
     * 方法二：快慢指针，空间复杂度为o(1)
     * 思想：两个指针从同一个位置出发，让快指针前进两格、慢指针只前进一格，如果是环形的则两个指针一定会相遇的
     *
     * @param head
     * @return
     */
    public static boolean hasCycle1(ListNode head) {
        //初始化哨兵
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        //初始化快慢指针
        ListNode slow = dummy;
        ListNode fast = head;

        while (fast != slow){
            if (fast == null || fast.next == null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        return true;
    }

    /**
     * 方法一：垃圾方法，时间空间复杂度都很高，空间复杂度为o(n)
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head) {
        //初始化哨兵
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;

        Map<ListNode, Integer> map = new HashMap<>();
        while (node.next != null) {
            map.put(node, map.getOrDefault(node, 0) + 1);
            //只有map里面存在这对kv，并且v的值大于1，才能说有重复的值即存在环形链表
            if (map.containsKey(node) && map.get(node) > 1) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}